package linear

// 10种基本的排序算法;
// 就是背也要记住  插入 堆 归并 快速;
// 选泡插
// 快归堆希统计基

// SelectSort 选择排序 最简单 最没用;
// 依次查找最小的数 这个是严格小于;  T=O(NN) 不稳定的; 2 5 5 2 8  存在一个就是不稳定;
func SelectSort(nums []int) {
	for i := 0; i < len(nums)-1; i++ {
		lowest := i
		for j := i + 1; j < len(nums); j++ {
			if nums[j] < nums[lowest] {
				lowest = j
			}
		}
		nums[i], nums[lowest] = nums[lowest], nums[i]
	}
}

// BubbleSort 冒泡排序 每一趟扫描交换 都可以把最大的扫描出来
// 两两比较, 一轮循环之后 最大的就是到尾部位置, 然后一直重复即可; 稳定排序;  O(NN)
func BubbleSort(arr []int) {
	for t := 0; t < len(arr); t++ {
		for c := 0; c < len(arr)-t-1; c++ {
			if arr[c] > arr[c+1] {
				arr[c], arr[c+1] = arr[c+1], arr[c]
			}
		}
	}
}

// InsertionSort 插入排序 算法的入门  O(n^2); 反向冒泡 - 稳定排序, 比 冒泡的效率快很多; 前面的数组有序效率很高;
// n   在[0, n) 总是有序的 把第n个数 和前面有序的比较 严格小于 前面的就交换, 然后选择有序的位置; 可以不交换
func InsertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		tmp, j := arr[i], i
		// 往前比较;
		for ; j > 0 && arr[j-1] > tmp; j-- {
			arr[j] = arr[j-1]
		}
		arr[j] = tmp
	}
}

// -------------------------------------------------------------------------------------------------

// ShellSort 希尔排序;   基于插入排序 优化了间隔; 先写出插入排序 然后使用 一个 3h + 1 序列
// 改进的插入排序, 间隔大 比较的次数小; 间隔小, 比较的距离小; O(n^1.3)
func ShellSort(nums []int) {
	h := 1
	for h < len(nums) {
		h = 3*h + 1
	}

	for ; h >= 1; h = (h - 1) / 3 {
		for i := 0; i < len(nums); i = i + h {
			tmp, j := nums[i], i
			// 往前比较;
			for ; j > 0 && nums[j-h] > tmp; j = j - h {
				nums[j] = nums[j-h]
			}
			nums[j] = tmp
		}
	}
}

// MergeSort conquer and merge;
// 调用这个方法保证 [left, right] 这个区间的切片有序
func MergeSort(arr []int) []int {
	// 如果已经分到了最少一个单体的时候 就是直接把 所有的数字 拆开, 直接返回这是拆到最完整
	// a[1] 可以直接返回, a[2] 0 1
	if len(arr) == 1 {
		return arr
	}

	// 左一半有序 右一半有序 然后对左右进行merge
	// 左右的一半 开始二分 >> 这才是移位运算
	// 0 0 || 1 1    移位运算的优先级 prior to +-
	// mid := (len(arr) - 1) >> 1
	// 如果是长度 /2 我们知道 如果是偶数 直接返回其 1/2; 如果是奇数, 返回一个大 一个小的两部分, 其实两部分你分给谁都是一样的;
	// 奇数/2 相当于 拿到最后一个, 然后 equally divided. 然后把多的那一个 补给后面的 subArray;

	// [a:b] 这种表示 a: 索引; b: offset偏移量;
	// 如果是 索引, 01 这种情况 会出现 死循环, (2-1) >> 1 == 0, 索引可以 出现0, 但是长度不行;
	mid := len(arr) >> 1
	// 左右边界 因为是整除 向下取证, 这里需要 右边 + 1
	lArray := MergeSort(arr[:mid]) // 这里出现 death loop; len = 2
	rArray := MergeSort(arr[mid:])

	// 两个有序数组完成 MergeTwoSortedArr;
	return MergeTwoSortedArr(lArray, rArray)
}

// HeapSort 使用的堆排序
// 堆得概念, 堆就是 完全二叉树 从上到下 从左到右 排序, 和满二叉树一样的序号
// i 子节点 2i + 1; 2i + 2 这是一颗子树
// 4 6 8 5 9
// 升序是大顶堆
func HeapSort(arr []int) {
	// 如何构建一个堆
	// 从下到上 从右到左 逆序完成调整 获取最后一个非叶子节点
	// formula strictly prove:
	// 左: （len - 1） >> 1;
	// 右： len >> 1 - 1,        移位运算大于加减运算
	for leaf := len(arr)>>1 - 1; leaf >= 0; leaf-- {
		adjustHeap(arr, leaf, len(arr))
	}

	// 然后再对堆进行调整
	for end := len(arr) - 1; end >= 0; end-- {
		arr[end], arr[0] = arr[0], arr[end]
		adjustHeap(arr, 0, end)
	}
}

func adjustHeap(arr []int, i, len int) {
	// 从这个节点的左节点开始 到有节点依次
	for j := 2*i + 1; j < len; j = 2*j + 1 {
		// 可以 这里这个k的移动 ojbk
		if j+1 < len && arr[j+1] > arr[j] {
			// 直接右移
			j++
		}

		if arr[j] > arr[i] {
			// 那个这个最大值应该怎么办呢？ 直接将 子节点赋值给 父节点

			arr[i], arr[j] = arr[j], arr[i]
		}
	}
}

// FastSort arr[left, right]
func FastSort(arr []int, left, right int) {
	// 处理边界问题
	if left >= right {
		return
	}

	// 这个值是谁？ 其实取第一个 和 后面的都是一样的;
	// 模拟如果是 a[2] = {1, 0}  0 1
	tmp := arr[left]
	i, j := left, right

	for i != j {
		// 先从后面找到第一个小于第一个 pivot 的值交换
		for ; j > i; j-- {
			if arr[j] < tmp {
				arr[i], arr[j] = arr[j], arr[i]
				break
			}
		}

		for ; j > i; i++ {
			if arr[i] > tmp {
				arr[i], arr[j] = arr[j], arr[i]
				break
			}
		}
	}

	// 上面找到了 pi`vot 然后递归处理左 右
	FastSort(arr, left, i-1)
	FastSort(arr, i+1, right) // Bugs: [0, 1]
}
